package _dp

import org.junit.Assert
import org.junit.Test

/*
https://leetcode.cn/problems/fibonacci-number/description/
https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html

509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。


示例 1：
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
 */
class leetcode_509 {
    @Test
    fun test_1() {
        val actual = fib(2)
        val expect = 1
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_2() {
        val actual = fib(3)
        val expect = 2
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_4() {
        val actual = fib(4)
        val expect = 3
        Assert.assertEquals(expect, actual)
    }

    fun fib(n: Int): Int {
        // return fib1(n)
        // return fib2(n)
        return fib3(n)
    }

    fun fib1(n: Int): Int {
        /*
            动态规划
            // T - N
            // S - N
         */
        if (n == 0) {
            return 0
        }
        if (n == 1) {
            return 1
        }

        // 1 确定数组，以及下标含义
        // 数组 = F(n) valuie，i - n
        var dp: IntArray = IntArray(n + 1)
        // 2 递推公式
        // 3 初始化数组
        dp[0] = 0
        dp[1] = 1

        // 4 遍历顺序
        for (i in 2..n) {
            dp[i] = dp[i - 1] + dp[i - 2] // 2递推公式

            // 5 打印数组
            println("F($i) = F(${i - 1}) + F(${i - 2}) = ${dp[i-1]} + ${dp[i-2]} = ${dp[i]}")
        }
        return dp[n]
    }

    fun fib2(n: Int): Int {
        /*
           动态规划
           优化：不用数组，用3个变量
           T - N
           S - 1
        */
        if (n == 0) {
            return 0
        }
        if (n == 1) {
            return 1
        }
        var f_n: Int = 0
        var f_n_1 = 1
        var f_n_2 = 0
        for (i in 2..n) {
            f_n = f_n_1 + f_n_2
            f_n_2 = f_n_1
            f_n_1 = f_n
        }
        return f_n
    }

    fun fib3(n: Int): Int {
        /*
        递归法
        树深 - N
        T - 2 的N次方
        S - N (算上了编程语言中实现递归的系统栈所占空间)
        */
        // 确认终止条件
        if (n == 0) {
            return 0
        }
        if (n == 1) {
            return 1
        }
        val result: Int = fib3(n - 1) + fib3(n - 2)
        return result
    }
}